package hzk.codex2016.list;

public class LinkedLists_reverse {
	/**
	 * https://leetcode.com/problems/reverse-linked-list/
	 * 
	 * @param head
	 * @return
	 */
	public ListNode reverseList(ListNode head) {
		if (head == null)
			return null;
		ListNode pre = head, p = pre.next, tmp;
		head.next = null;
		while (p != null) {
			tmp = p.next;
			p.next = pre;
			pre = p;
			p = tmp;
		}
		return pre;

	}

	// a recursive alternative method
	public ListNode reverseList2(ListNode head) {
		if (head == null)
			return null;
		ListNode tail, p = head.next;
		if (p == null)
			return head;
		tail = reverseList(p);
		p.next = head;
		head.next = null;
		return tail;

	}

	/**
	 * https://leetcode.com/problems/swap-nodes-in-pairs/
	 * 
	 * @param head
	 * @return
	 */
	public ListNode swapPairs(ListNode head) {
		if (head==null) return null;
		ListNode fakeHead=new ListNode(0),pre=fakeHead,p=head,q,tmp;
		//head.next=null;
		while (p!=null){
			q=p.next;
			if (q==null){
				pre.next=p;
				break;
			}
			p.next=null;
			tmp=q.next;
			q.next=p;
			pre.next=q;
			pre=p;
			p=tmp;			
		}
		return fakeHead.next;
	}

	static ListNode ll(int... vals) {
		return ListNode.asList(vals);
	}

	public static void main(String[] args) {
		LinkedLists_reverse p = new LinkedLists_reverse();
		System.out.println(p.reverseList(ll(1, 3, 5, 7, 9, 11, 14, 17, 20, 22)));
		System.out.println(p.reverseList(ll()));
		System.out.println(p.reverseList(ll(3)));
		System.out.println(p.reverseList(ll(3, 7)));
		System.out.println(p.reverseList(ll(2, 5, 7)));
		System.out.println("---");
		for (ListNode e:TestDatas.orderedLists){
			//System.out.println(e);
			System.out.println(p.swapPairs(e));
		}
	}
}
